|
The graph isomorphism problem is the computational problem of determining whether two finite graphs are isomorphic. Besides its practical importance, the graph isomorphism problem is a curiosity in computational complexity theory as it is one of a very small number of problems belonging to NP neither known to be solvable in polynomial time nor NP-complete: it is one of only 12 such problems listed by , and the only one of that list whose complexity remains unresolved. It is known that the graph isomorphism problem is in the low hierarchy of class NP, which implies that it is not NP-complete unless the polynomial time hierarchy collapses to its second level. At the same time, isomorphism for many special classes of graphs can be solved in polynomial time, and in practice graph isomorphism can often be solved efficiently. This problem is a special case of the subgraph isomorphism problem, which is known to be NP-complete. It is also known to be a special case of the non-abelian hidden subgroup problem over the symmetric group. ==State of the art== The best current theoretical algorithm is due to , and is based on the earlier work by combined with a ''subfactorial'' algorithm due to . The algorithm relies on the classification of finite simple groups. Without CFSG, a slightly weaker bound 2O(√''n'' log2 ''n'') was obtained first for strongly regular graphs by , and then extended to general graphs by . Improvement of the exponent √''n'' is a major open problem; for strongly regular graphs this was done by . For hypergraphs of bounded rank, a subexponential upper bound matching the case of graphs, was obtained by . On November 10, 2015, Babai gave a talk during which he claimed to have found a better algorithm, with the execution time being just slightly more than polynomial. On a side note, the graph isomorphism problem is computationally equivalent to the problem of computing the automorphism group of a graph, and is weaker than the permutation group isomorphism problem, and the permutation group intersection problem. For the latter two problems, obtained complexity bounds similar to that for graph isomorphism. There are several competing practical algorithms for graph isomorphism, due to , , , etc. While they seem to perform well on random graphs, a major drawback of these algorithms is their exponential time performance in the worst case. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「graph isomorphism problem」の詳細全文を読む スポンサード リンク
|